/**
 * 234.回文链表
 */
public class Exerciser2 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public boolean isPalindrome(ListNode head) {
        // 寻找中间节点，翻转链表，查询是否是回文链表
        // 寻找中间节点
        ListNode mid = midNode(head);
        // 翻转链表
        ListNode head2 = reverseNode(mid);
        // 判断是否是回文
        while(head2 != null) {
            if(head.val != head2.val) {
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    public ListNode midNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseNode(ListNode mid) {
        // 这里pre需要设置为null，否则判断回文串的时候呢，不知道何时进行结束
        ListNode pre = null;
        ListNode cur = mid;
        while(cur != null) {
            ListNode cN = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cN;
        }
        return pre;
    }
}
